/*
 * 0065. 两个排序数组的中位数
 * 两个排序的数组A和B分别含有m和n个数，找到两个排序数组的中位数，要求时间复杂度应为O(log (m+n))。
 * https://www.lintcode.com/problem/median-of-two-sorted-arrays/description
 * 
 * 样例
 * 给出数组A = [1,2,3,4,5,6] B = [2,3,4,5]，中位数3.5
 * 给出数组A = [1,2,3] B = [4,5]，中位数 3
 * 
 * 挑战
 * 时间复杂度为O(log n)
 * 
 * 2018.06.30 @jeyming
 */
package median_of_two_sorted_arrays_0065;

import java.util.ArrayList;
import java.util.List;

public class Median_of_two_sorted_arrays_0065 {
    /*
     * @param A: An integer array
     * @param B: An integer array
     * @return: a double whose format is *.5 or *.0
     */
    public double findMedianSortedArrays(int[] A, int[] B) {
        // write your code here
    	List<Integer> list = new ArrayList<Integer>();
    	int numA = A.length;
    	int numB = B.length;
    	int cntA = 0;
    	int cntB = 0;
    	while((cntA < numA) || (cntB < numB)) {
    		if((cntA == numA) && (cntB < numB)) {
    			list.add(B[cntB++]);
    		} else if((cntA < numA) && (cntB == numB)) {
    			list.add(A[cntA++]);
    		} else {
    			if((A[cntA] < B[cntB])) {
        			list.add(A[cntA++]);
        		} else if(A[cntA] > B[cntB]) {
        			list.add(B[cntB++]);
        		} else {
        			list.add(A[cntA++]);
        			list.add(B[cntB++]);
        		}
    		}
    	}
    	int tmp = list.size() / 2;
    	if(list.size() % 2 == 0) {
    		return ((double)(list.get(tmp) + list.get(tmp - 1))) / 2;
    	} else {
    		return (double)list.get(tmp);
    	}
    }

	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
